package main

// 什么是 连通分量
// 同一颜色，上下左右四个方向相连的
// 什么是 联通分量的边界？ 必须满足的条件，是连通分量！再满足下面一个即可
// 1. 网格上,下,左,右边界位置 的联通分量， 可以当做连通分量的边界
// 2. 联通分量的四个方向的相邻格子 和自身 不是一个 色， 它也是 连通分量的边界
// 使用指定的 color 对所有 连通分量的边界 进行着色

// 使用BSF进行。 因为指定一个位置 grid[row][col]，可以先求得它的 连通分量，
// 再把它的联通分量 中 是边界的给依次 着色。
import "container/list"

func colorBorder(grid [][]int, row int, col int, color int) [][]int {
	// 定义队列
	d := list.New()
	d.PushBack([2]int{row, col})
	oldColor := grid[row][col]
	// 定义上下左右动作
	dir := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	// 定义判重数组并初始化
	used := make([][]bool, len(grid))
	for i, _ := range used {
		used[i] = make([]bool, len(grid[0]))
	}
	used[row][col] = true
	for d.Len() > 0 {
		node := d.Remove(d.Front()).([2]int)
		// 2. 对四个相邻方向进行判断,当四个相邻方向格子颜色和当前不一样，当前格子也是边界
		isBoard := false
		for _, ac := range dir {
			x := node[0] + ac[0]
			y := node[1] + ac[1]
			// 如果越界，已遍历过，退出
			if x < 0 || y < 0 ||
				x >= len(grid) || y >= len(grid[0]) ||
				used[x][y] == true {
				continue
			}
			if grid[x][y] == oldColor {
				d.PushBack([2]int{x, y})
				// 维护判重数组, 要放到这里！
				used[x][y] = true
				continue
			}
			isBoard = true
		}
		// 1. 判断当前是否在边界, 或者四周颜色不等与 它
		if node[0] == 0 || node[0] == len(grid)-1 ||
			node[1] == 0 || node[1] == len(grid[0])-1 ||
			isBoard {
			grid[node[0]][node[1]] = color
		}
	}
	return grid
}
